#include <iostream>
#include <cstdlib>
#include <stack>

typedef int ElemType;

class BitNode {
  public:
    BitNode() = default;
    explicit BitNode(ElemType _data) : data(_data), lchild(nullptr), rchild(nullptr) {}

  public:
    ElemType data;
    BitNode *lchild, *rchild;
};

BitNode* createBitTree()
{
  BitNode* tree = new BitNode(13);
  tree->lchild = new BitNode(10);
  tree->lchild->lchild = new BitNode(9);
  tree->lchild->rchild = new BitNode(12);
  tree->lchild->rchild->lchild = new BitNode(11);
  tree->rchild = new BitNode(15);
  tree->rchild->rchild = new BitNode(9);
  return tree;
}

void freeBitTree(BitNode* tree)
{
  if (tree != nullptr) {
    freeBitTree(tree->lchild);
    tree->lchild = nullptr;
    freeBitTree(tree->rchild);
    tree->rchild = nullptr;
    free(tree);
  }
}

void visitNode(BitNode* tree)
{
  if (tree != nullptr) {
    std::cout << tree->data << std::endl;
  }
}

void inOrder(BitNode* tree)
{
  if (tree != nullptr) {
    inOrder(tree->lchild);
    visitNode(tree);
    inOrder(tree->rchild);
  }
}

void postOrder(BitNode* tree)
{
  if (tree != nullptr) {
    postOrder(tree->lchild);
    postOrder(tree->rchild);
    visitNode(tree);
  }
}

// 删除二叉树根节点，用右子树先序遍历首节点替换
BitNode* delRoot(BitNode* tree)
{
  if (tree == nullptr) {
    return nullptr;
  }

  BitNode* new_tree = nullptr;
  if (tree->lchild == nullptr) {
    new_tree = tree->rchild;
  } else if (tree->rchild == nullptr) {
    new_tree = tree->lchild;
  } else {
    // 查找右子树最小值节点及其父节点
    BitNode* rmin_fn = tree;
    BitNode* rmin = tree->rchild;
    while (rmin->lchild != nullptr) {
      rmin_fn = rmin;
      rmin = rmin->lchild;
    }

    // 替换tree节点
    rmin->lchild = tree->lchild;
    if (rmin != tree->rchild) {
      rmin_fn->lchild = rmin->rchild;
      rmin->rchild = tree->rchild;
    }
    new_tree = rmin;
  }

  free(tree);
  return new_tree;
}

// 递归方式查找节点并删除
BitNode* delTreeNodeRec(BitNode* tree, ElemType data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (tree->data == data) {
    return delRoot(tree);
  }

  tree->lchild = delTreeNodeRec(tree->lchild, data);
  tree->rchild = delTreeNodeRec(tree->rchild, data);
  return tree;
}

// 非递归方式查找节点并删除
BitNode* delTreeNode(BitNode* tree, ElemType data)
{
  if (tree == nullptr) {
    return nullptr;
  }

  if (tree->data == data) {
    return delRoot(tree);
  }

  BitNode* cur = nullptr;

  // 使用后序遍历非递归方式查找待删除节点
  std::stack<BitNode*> st;
  BitNode* p = tree;
  BitNode* pre = nullptr;
  while ((p != nullptr) || !st.empty()) {
    if (p != nullptr) {
      st.push(p);
      p = p->lchild;
    } else {
      p = st.top();
      if (p->rchild != nullptr && p->rchild != pre) { 
        p = p->rchild; 
      } else {
        if (p->data == data) {
          cur = p;
          st.pop();
          break;
        }
        st.pop();
        pre = p;
        p = nullptr;
      }
    }
  }

  // 找到目标节点，可进行节点删除操作
  BitNode* par = nullptr;
  if (cur != nullptr) {
    if (!st.empty()) {
      par = st.top();
    }

    if (par != nullptr) {
      if (par->lchild == cur) {
        par->lchild = delRoot(cur);
      }
      if (par->rchild == cur) {
        par->rchild = delRoot(cur);
      }
    }
  }

  return tree;
}

int main(int argc, char* argv[])
{
  if (argc != 2) {
    return -1;
  }
  BitNode* tree = createBitTree();
  inOrder(tree);
  std::cout << std::endl;

  // tree = delTreeNode(tree, atoi(argv[1]));
  // inOrder(tree);
  // postOrder(tree);
  // std::cout << std::endl;

  tree = delTreeNodeRec(tree, atoi(argv[1]));
  inOrder(tree);
  postOrder(tree);
  std::cout << std::endl;

  freeBitTree(tree); 
  tree = nullptr;
  return 0;
}

